﻿#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> vv;
        queue<TreeNode*> q;
        int levelsize = 1;
        if (root == nullptr) return vv;
        q.push(root);
        while (levelsize > 0)
        {
            vector<int> v;
            while (levelsize--)
            {
                if (root->left) q.push(root->left);
                if (root->right) q.push(root->right);
                TreeNode* front = q.front();
                v.push_back(front->val);
                q.pop();
            }
            vv.push_back(v);
            levelsize = q.size();
        }
        return vv;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool IsInTree(TreeNode* t, TreeNode* x)
    {
        if (t == nullptr)
            return false;
        return t == x || IsInTree(t->left, x) || IsInTree(t->right, x);
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr)
            return nullptr;
        if (root == p || root == q)
            return root;
        //自此开始要么都在左,要么都在右
        bool pInleft = IsInTree(root->left, p);
        bool pInright = !pInleft;
        bool qInleft = IsInTree(root->left, q);
        bool qInright = !qInleft;

        if ((qInleft && pInright) || (qInright && pInleft)) return root;
        else if (pInleft && qInleft) return lowestCommonAncestor(root->left, p, q);
        else return lowestCommonAncestor(root->right, p, q);
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* build(vector<int>& inorder, vector<int>& postorder, int& post, int inbegin, int inend)
    {
        if (inbegin > inend) return nullptr;
        TreeNode* newnode = new TreeNode(postorder[post]);
        int rooti = inbegin;
        while (rooti <= inend)
        {
            if (postorder[post] == inorder[rooti])
                break;
            else
                rooti++;
        }
        post--;
        newnode->right = build(inorder, postorder, post, rooti + 1, inend);
        newnode->left = build(inorder, postorder, post, inbegin, rooti - 1);

        return newnode;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int post = postorder.size() - 1;
        return build(inorder, postorder, post, 0, inorder.size() - 1);
    }
};